package cn.leonis.leetcode;

/**
 * @author Tobi
 * @time 2021-07-10 10:10 AM
 * 二分查找，返回找到的索引,实现二分查找的前提是，该数组是有序的
 */
public class BinarySearchSolution {

    public static void main(String[] args) {
        int[] nums = new int[]{-3, 0, 1, 5, 9, 12};
        int target = 9;
        BinarySearchSolution solution = new BinarySearchSolution();
        System.out.println(solution.binarySearch(nums, target));
    }

    /**
     * 解法一：时间复杂度为O(nlogn)
     * @param nums
     * @return
     */
    public int binarySearch(int[] nums, int target) {

        int length = nums.length;

        // 左指针
        int pl = 0;

        // 右指针
        int pr = length - 1;

        while (pl <= pr) {
            // 先将范围内的值除以2，然后再加上左边的指针，得出来的值就是现在的中间坐标
            int mid = pl + (pr - pl) / 2;
            if (nums[mid] < target) {
                pl = mid + 1;
            }else if (nums[mid] > target) {
                pr = mid - 1;
            }else {
                return mid;
            }
        }

        return -1;
    }
}
